Encryption methods are broadly classified into a public key encryption method and a common key encryption method. The public key encryption method is a method using different keys for encryption and decryption. This is a method for securing safety by making a key (secret key) for decrypting an encrypted text secret only to a receiver although a key (public key) for encrypting a text is made public. In contrast, the common key encryption method is a method using the same key (secret key) for both encryption and decryption. This is a method for securing safety by implementing the secret key as information unknown to third parties except for a transmitter and a receiver.
Techniques in the encryption field include cryptanalysis. Cryptanalysis is a technique for estimating secret information such as a secret key or the like on the basis of obtainable information such as an encrypted text or the like. Cryptanalysis includes various techniques. A method called a power analysis attack (hereinafter referred to as PA) is a technique that has been recently receiving attention. PA is a technique devised by Paul Kocher in 1998. This is a technique for estimating key information within an encryption processor by collecting/analyzing power consumption data when various pieces of input data are given to the encryption processor included in an embedded apparatus such as a smart card or the like. It is known that a secret key can be estimated from an encryption processor by using PA in both public key encryption and secret key encryption.
PA includes two types of analyses such as a single power analysis (hereinafter referred to as SPA), and a differential power analysis (hereinafter referred to as DPA)). SPA is a method for estimating a secret key on the basis of a characteristic of single piece of power consumption data in an encryption processor, whereas DPA is a method for estimating a secret key by analyzing differences among many pieces of power consumption data. Normally, DPA is said to be stronger analysis. The following paper was announced as a representative of cryptanalysis using SPA and DPA. Documents such as Non-Patent Document 1 listed below describe cryptanalysis using DPA for public key encryption such as RSA or the like. Moreover, Non-Patent Document 2 listed below describes cryptanalysis using SPA and DPA for DES (Data Encryption Standards) currently used as a standard in common key encryption methods. In addition to DES, also Rijndael that is a common key encryption method is expected to be used as a standard in the next generation, and documents such as Non-Patent Document 3 listed below and the like point out the possibility of decryption using DPA.
Cryptanalytic technology using PA has been receiving attention as an especially effective method, and diverse cryptanalytic methods have been studied. Not only cryptanalytic technology but also countermeasures for preventing cryptanalysis using PA has made a progress, and has been focused as important technology as well as cryptanalytic technology.
FIG. 1 illustrates a normal configuration of a common key encryption process. Normally, the common key encryption process is composed of two processes such as a round process and expanded key generation. With the expanded key generation, a plurality of pieces of data called expanded keys (hereinafter denoted as expanded key 0, expanded key 1, . . . , expanded key N) are generated from an input secret key, and the generated data are output to the round process. By inputting these expanded keys and a plaintext to the round process, a transformation for encryption is performed, and an encrypted text is output.
AES (Advanced Encryption Standards) is known as a representative common key encryption algorithm, and AES is made public as Non-Patent Document 4 listed below.
FIG. 2 illustrates a configuration of AES.
AES is an algorithm using 128 bits as an encryption unit. Namely, a 128-bit encrypted text is generated from a 128-bit plaintext. A secret key is selectable from among three types such as 128 bits, 192 bits and 256 bits. By executing the expanded key process, N+1 128-bit expanded keys are generated from a secret key. An AES round process is composed of four types of processes such as RoundKey, Subbyte, ShiftRow and MixColumn. In RoundKey among them, an expanded key is used. A plaintext is input to the round process, which is repeated by N−1 times in order of RoundKey, Subbyte, ShiftRow and MixColumn. Then, the processes of RoundKey, Subbyte, ShiftRow and RoundKey are executed to output an encrypted text. The number of repetitions N varies depending on a bit length of a secret key. For 128 bits, N=10. For 192 bits, N=12. For 256 bits, N=14. FIGS. 3 to 6 illustrate the RoundKey process, the Subbyte process, the MixColumn process, and the ShiftRow process, respectively.
<Secret Key Cryptanalytic Method Using DPA>
A secret key cryptanalytic method using DPA is described below. DPA is a method for cryptanalyzing a secret key by measuring power consumed for the round process of FIG. 1. A process configuration of enabling cryptanalysis of a secret key by using DPA in common key encryption is described below without restricting to AES. Normal common key encryption is implemented by configuring the round process with a combination of an expanded key XOR process (FIG. 7), a linear transformation process (FIG. 8) and a nonlinear transformation process (FIG. 3), and by repeating the round process by a plurality of times. As illustrated in FIG. 7, the expanded key XOR process is a process for outputting a computation result Z of an exclusive OR (XOR) operation of input data X with an expanded key K. FIG. 8 illustrates the linear transformation process. This is a process for outputting Z that satisfies Z=L (X) where X is input data. At this time, L satisfies the following equation where X and Y are arbitrary values.L(X⊕Y)=L(X)⊕L(Y)
(In the following description, the symbol ⊕ is replaced with ◯)
Specifically, a bit permutation process like ShiftRow illustrated in FIG. 6, a matrix operation like MixColumn illustrated in FIG. 5, and other operations correspond to this equation. FIG. 9 illustrates the nonlinear transformation process. This is a process for outputting Z that satisfies Z=W(X) where X is input data. At this time, W does not satisfy (namely, nonlinear) an equation W(X◯Y)=W(X)◯W(Y) where X and Y are arbitrary values. Specifically, this process is implemented with a nonlinear transformation table index called Sbox in many cases. Input X is divided into u pieces (X=x0x1 . . . xu−1), represented by zj=wj(xj) is calculated by using Sbox wj, and Z is output by being again combined as Z=z0z1 . . . zu−1.
A cryptanalyzing method using DPA for common key encryption implemented by combining the above described processes is described next.
An example where the expanded key K can be decrypted by using DPA for a process of FIG. 10 implemented by combining the processes of FIGS. 7 and 9 is described as the simplest example. The configuration illustrated in FIG. 10 is equivalent to the structure implemented by combining RoundKey (FIG. 3) and Subbyte (FIG. 4) of AES.
FIG. 11 illustrates a configuration implemented by extracting only a bit related to an input/output of Wj from the configuration illustrated in FIG. 10. In FIG. 11, assume that mj, kj and wj are a known value such as a plaintext or the like, an unknown value, and a known Sbox table, respectively. Estimation of the expanded key kj by using DPA is described based on this assumption.
DPA is composed of two stages such as a measurement of power consumption data, and an expanded key analysis using differential power data. With the measurement of power consumption data, data of power consumption of an encryption processor when a plaintext is given is measured as a power consumption curve illustrated in FIG. 12 with an oscilloscope or the like. Such a measurement is repeated while varying the value of a plaintext, and the measurement is terminated when data of a sufficient number of measurements is obtained. A set of power consumption curves obtained with this series of measurements is defined as G.
The expanded key analysis using power consumption curves is described next. Assume kj=k′j for the expanded key kj used in the encryption process. Since mj and wj are known, the set G can be classified into the following two types of subsets such as G0(k′j) and G1(k′j) in accordance with the e-th bit value of assumed wj(mj◯k′j).G0(k′j)=eth bit value of {G|zj=wj(mj◯k′j)=0}  (1)G1(k′j)=eth bit value of {G|zj=wj(mj◯k′j)=1}  (2)
Then, the following differential power curve DG(k′j) is created.DG(k′j)=(average of power consumption curves belonging to the subset G1)−(average of power consumption curves belonging to the subset G0)  (3)
If this assumption is correct, namely, if k′j=kj, a spike illustrated in FIG. 13A appears. If this assumption is incorrect, namely, if k′j≠kj, a flat curve where a spike does not appear is obtained as illustrated in FIG. 13B. Accordingly, if the differential power curve illustrated in FIG. 13A is obtained from the assumed k′j, it means that the expanded key kj can be cryptanalyzed. By performing such cryptanalysis of kj for each j, the expanded key illustrated in FIG. 10 can be finally decrypted. This cryptanalysis is repeated for expanded key 0, expanded key 1, . . . , expanded key N, whereby a secret key can be decrypted. For AES, the initial value of an expanded key is the value of a secret key unchanged in terms of the nature of the algorithm. Therefore, by decrypting the expanded key 0 if the secret key is 128 bits, or by decrypting the expanded keys 0 and 1 if the secret key is 256 bits, the entire secret key can be decrypted.
The reason why the spike appears in the differential power curve DG(k′1) if k′j=kj is described next. If k′j=kj, an equation (4) is satisfied for Zj when G is classified into G0(k′j) and (G1(k′j) according to the equations (1) and (2).(average hamming weight of zj belonging to G1)−(average hamming weight of zj belonging to G0)=1  (4)
In the meantime, if k′j≠kj, the equation (4) is not satisfied, and the set G is randomly classified. Therefore, an equation (5) is satisfied.(average hamming weight of zj belonging to G0)−(average hamming weight of zj belonging to G0)=0  (5)
A hamming weight is the number of bits having a value “1” when a certain value is represented with bit values. For example, the hamming weight of a bit value (1101)2 is 3.
Accordingly, a difference occurs between average hamming weights of the load value zj of G1(k′j) and G0(k′j) if the equation (4) is satisfied. However, if the equation (5) is satisfied, a difference does not occur between the average hamming weights of the load value zj of G1(k′j) and G0(k′j).
Normally, power consumption is considered to be proportional to a hamming weight of a data value. Experimental results that prove this to be correct are referred to in documents such as Non-Patent Document 5 listed below and the like.
Accordingly, if k′j=kj, a difference of power consumption appears as a spike in a differential power curve when the equation (4) is satisfied. However, a spike does not appear and a differential power curve becomes flat when the equation (5) is satisfied.
DPA against the simplest structure illustrated in FIG. 10 has been described. However, it has been proved that such a method can be implemented even if the linear transformation of FIG. 9 is inserted.
FIG. 14 illustrates a structure implemented by generalizing the structure of FIG. 10. This is a processing structure implemented by inserting two linear transformation processes L1 and L2 before and after the key XOR process. By respectively implementing L1, L2, and wj, for example, as a function of outputting an input unchanged, a bit permutation function, and Sbox called a B function of SC2000, FIG. 14 illustrates a structure equivalent to SC2000. For specifications of SC2000, see Non-Patent Document 6 listed below. Since L2 is a bit permutation function, the process of FIG. 14 can be transformed into the same process as that of FIG. 11 by considering the structure obtained by extracting only a bit related to an input/output of wj, and an expanded key K can be decrypted by using DPA similar to the above described one.
With the above described method, DPA is applied by focusing an Sbox output during the linear process. In addition, a method for applying DPA by focusing a value obtained immediately after XORing an input mj and a key kj (output value of the XOR process of a key) or an input value xj to the Sbox is known (Non-Patent Document 7 listed below).
In summary, the secret key K is estimated with DPA if the following conditions are satisfied (these DPA attack conditions are referred to also in Patent Document 1 listed below).
DPA-1. If an input M is known and controllable, the key K is unknown and fixed and a transformation of Sbox wj is known, DPA can be performed by measuring a power consumption curve of a portion A (output of Sbox wj) illustrated in FIG. 15.
DPA-2. If the input M is known and controllable and the key K is unknown and fixed, DPA can be performed by measuring a power consumption curve of a portion B (a write of the output of the XOR process of a key) illustrated in FIG. 15.
DPA-3. If the input M is known and controllable and the key K is unknown and fixed, DPA can be performed by measuring a power consumption curve of a portion C (loading of an input value for indexing Sbox wj) illustrated in FIG. 15.
<Secret Key Decryption Method Using SPA>
A secret key decryption method using SPA is described below. This attack observes power consumption of a multiplication process represented byc=a{circle around (×)}b 
({circle around (×)} is a symbol that represents a multiplication. The symbol {circle around (×)} is hereinafter replaced with ⊚ in this specification) where {circle around (×)} is a symbol that represents a multiplication. In an AES process, a multiplication process when a, b and c are an element of GF(28) or GF(((22)2)2) is executed in a calculation (FIG. 23) of a composite field to be described later. If “0” is input to as b that is input data, a multiplication by 0, namely, an operation of 0=0⊚b or 0=a⊚0 is performed (hereinafter referred to as a zero multiplication). If a comparison is made between a power consumption waveform of the zero multiplication and a power consumption waveform of a multiplication if a and b are not zero (hereinafter referred to as a non-zero multiplication), it is known that the former becomes a very special waveform. Namely, a distinction can be made with SPA between the zero multiplication and the non-zero multiplication in the multiplication process. By using this nature, a secret key can be decrypted. This attack is referred to as zero multiplication SPA. The zero multiplication SPA is an attack method that can be executed only for an encryption processing apparatus using a multiplication process in its nature. For AES, this attack method can be executed only for an encryption processing apparatus using the Subbyte process implemented with a calculation (FIG. 23) of a composite field to be described later, and this attack cannot be performed for other encryption processing apparatuses.
FIG. 16 illustrates a circuit configuration of an encryption process that can be attacked with the zero multiplication SPA.
In FIG. 16, M is a value, such as a plaintext or the like, known to an attacker, and K is a value, such as a key or the like, unknown to the attacker. After the XOR operation of X=M◯K is performed, a multiplication process Z=X⊚Y with data Y is performed. The value of Y is a value unknown to the attacker. The attacker observes this operation with SPA, and observes whether or not the zero multiplication occurs in the operation of X⊚Y while changing the value of M. If the zero multiplication is observed, X=0. Namely, since M◯K=0 is proved, K=M, namely, the unknown K is proved to match M. As a result, K can be decrypted. To successfully perform this attack, the value of Y needs to be an arbitrary value other than “0”.
The zero multiplication SPA can be performed also for the circuit configuration illustrated in FIG. 17.
In FIG. 17, M is a value, such as a plaintext or the like, known to an attacker, and K is a value, such as a key or the like, unknown to the attacker. α is an arbitrary transformation function. The transformation may be either linear or nonlinear as long as an attacker can perform an inverse transformation α−1(0) for zero (namely, z that satisfies α(z)=0). After the XOR operation V=M◯K and an operation X=α(V) are performed, the multiplication process Z=X⊚Y by data Y is performed. The value of Y is a value unknown to the attacker. The attacker observes this process with SPA, and observes whether or not the zero multiplication occurs in the operation of X⊚Y while changing the value of M. If the zero multiplication is observed, X=0. Namely, since α(M◯K)=0, M◯K=z is proved. That is, K=M◯z is proved, and K can be therefore decrypted.
<Conventional Techniques>
As conventional DPA countermeasures, there is a technique for randomizing power consumption by taking countermeasures for an encryption process. The following two conventional examples are known as countermeasures using this technique. These examples are described below as conventional examples 1 and 2. Moreover, a method for reducing a Subbyte circuit in an AES circuit without DPA countermeasures is described in the following conventional example 3. The Subbyte circuit is implemented not with the multiplication process but with a table operation in the conventional examples 1 and 2. Therefore, these examples are safe from the zero multiplication SPA, and the DPA countermeasures to be taken functions as PA countermeasures unchanged.